package Leetcode.数组字符串;

import java.util.Collections;
import java.util.LinkedList;

/**
 * @ClassName 字符串解码
 * @since: 2023/8/15 14:52
 * @auth: kirito
 * @description:
 * 示例 1：
 *
 * 输入：s = "3[a]2[bc]"
 * 输出："aaabcbc"
 * 示例 2：
 *
 * 输入：s = "3[a2[c]]"
 * 输出："accaccacc"
 * 示例 3：
 *
 * 输入：s = "2[abc]3[cd]ef"
 * 输出："abcabccdcdcdef"
 * 示例 4：
 *
 * 输入：s = "abc3[cd]xyz"
 * 输出："abccdcdcdxyz"
 **/
public class 字符串解码 {
    int ptr; // 指针，用于在字符串中移动位置

    public String decodeString(String s) {
        LinkedList<String> stk = new LinkedList<String>(); // 使用链表作为栈
        ptr = 0; // 初始化指针位置

        while (ptr < s.length()) {
            char cur = s.charAt(ptr);

            if (Character.isDigit(cur)) {
                // 获取一个数字并进栈
                String digits = getDigits(s); // 获取连续的数字字符串
                stk.addLast(digits); // 将数字字符串加入栈中
            } else if (Character.isLetter(cur) || cur == '[') {
                // 获取一个字母或左括号并进栈
                stk.addLast(String.valueOf(s.charAt(ptr++))); // 将字母或左括号加入栈中
            } else {
                ++ptr; // 跳过右括号
                LinkedList<String> sub = new LinkedList<String>(); // 用于存储括号内的字符串
                while (!"[".equals(stk.peekLast())) { // 当栈顶元素不是左括号时
                    sub.addLast(stk.removeLast()); // 将栈顶元素移除并添加到sub中
                }
                Collections.reverse(sub); // 反转sub中的元素顺序，使得栈顶的元素为最先进入的
                stk.removeLast(); // 移除左括号

                // 此时栈顶为当前 sub 对应的字符串应该出现的次数
                int repTime = Integer.parseInt(stk.removeLast()); // 获取字符串应该出现的次数
                StringBuffer t = new StringBuffer(); // 用于构造重复后的字符串
                String o = getString(sub); // 获取括号内的字符串
                // 构造字符串
                while (repTime-- > 0) {
                    t.append(o); // 将括号内的字符串重复repTime次添加到t中
                }
                // 将构造好的字符串入栈
                stk.addLast(t.toString());
            }
        }

        return getString(stk); // 返回栈中的最终结果字符串
    }

    public String getDigits(String s) {
        StringBuffer ret = new StringBuffer();
        while (Character.isDigit(s.charAt(ptr))) {
            ret.append(s.charAt(ptr++)); // 将连续的数字字符添加到ret中
        }
        return ret.toString(); // 返回获取的数字字符串
    }

    public String getString(LinkedList<String> v) {
        StringBuffer ret = new StringBuffer();
        for (String s : v) {
            ret.append(s); // 将链表中的字符串按顺序添加到ret中
        }
        return ret.toString(); // 返回拼接后的字符串
    }
//-------------------------递归

    String src; // 输入字符串
//    int ptr; // 指针，用于在字符串中移动位置

    public String decodeString2(String s) {
        src = s; // 将输入字符串赋值给变量 src
        ptr = 0; // 初始化指针位置
        return getString(); // 调用辅助方法获取解码后的字符串
    }

    public String getString() {
        if (ptr == src.length() || src.charAt(ptr) == ']') {
            // String -> EPS，如果指针已经到达字符串末尾或者当前字符为右括号，则返回空字符串
            return "";
        }

        char cur = src.charAt(ptr); // 当前字符
        int repTime = 1; // 重复次数
        String ret = ""; // 构造的字符串结果

        if (Character.isDigit(cur)) {
            // String -> Digits [ String ] String，解析数字和括号内的字符串
            repTime = getDigits(); // 获取连续的数字值
            ++ptr; // 过滤左括号
            String str = getString(); // 递归解析括号内的字符串
            ++ptr; // 过滤右括号
            // 构造字符串
            while (repTime-- > 0) {
                ret += str; // 将括号内的字符串重复 repTime 次添加到结果中
            }
        } else if (Character.isLetter(cur)) {
            // String -> Char String，解析单个字母和后续的字符串
            ret = String.valueOf(src.charAt(ptr++)); // 获取当前字母并将指针向后移动一位
        }

        return ret + getString(); // 返回拼接后的字符串结果，并继续解析剩余的字符串
    }

    public int getDigits() {
        int ret = 0; // 数字结果
        while (ptr < src.length() && Character.isDigit(src.charAt(ptr))) {
            ret = ret * 10 + src.charAt(ptr++) - '0'; // 将连续的数字字符转换为整数值
        }
        return ret; // 返回数字结果
    }

}
